
//2560.打家劫舍IV
class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        // 二分 + DP
        // 使用二分来猜每一次的盗取能力 , 用DP来判断该盗取能力是否满足条件
        int n = nums.size();

        function<bool(int)> mecomd = [&](int val)
        {
            //判断在val能力的条件下,能否偷k个房子
            vector<int> f(n+1) ,g(n+1);         //f表示当前位置偷可以偷的最大数量,g表示当前位置不偷可以偷的最大数量
            for(int i = 1; i < n + 1; i++)
            {
                if(nums[i-1] > val)
                    g[i] = max(g[i-1],f[i-1]);
                else
                {
                    //当前位置可偷可不偷
                    g[i] = max(f[i-1] ,g[i-1]);
                    f[i] = g[i-1] + 1;
                }
            }
            for(int i = 0 ; i <= n ; i++)
                if(f[i] >= k || g[i] >= k) return true;

            return false;            
        };

        int right = ranges::max(nums) + 1;      // 使用开区间的二分
        int left = 0;
        while(left + 1 < right)
        {
            int mid = right - (right-left)/2;
            if(mecomd(mid)) right = mid;
            else left = mid;
        }
        return right;
    }
};